package site.zhouinfo.tree;

/**
 * 树状数组
 * <p>
 * 平常我们会遇到一些对数组进行维护查询的操作，比较常见的如，修改某点的值、求某个区间的和，而这两种恰恰是树状数组的强项！
 * 当然，数据规模不大的时候，对于修改某点的值是非常容易的，复杂度是O(1)，但是对于求一个区间的和就要扫一遍了，复杂度是O(N)，
 * 如果实时的对数组进行M次修改或求和，最坏的情况下复杂度是O(M*N)，当规模增大后这是划不来的！
 * 而树状数组干同样的事复杂度却是O(M*lgN)
 *
 * @author zhou
 * @create 2017-07-13 15:24
 * @email zhouinfo@qq.com
 * @blog blog.zhouinfo.site
 */
public class TreeArray {

    private static int n = 10;
    private static int[] tree = new int[n];

    /*
    * lowbit(k)就是把k的二进制的高位1全部清空，只留下最低位的1,
    * 比如10的二进制是1010,则lowbit(k)=lowbit(1010)=0010(2进制)，
    * 介于这个lowbit在下面会经常用到，这里给一个非常方便的实现方式，
    * 比较普遍的方法lowbit(k)=k&-k，这是位运算，
    * 我们知道一个数加一个负号是把这个数的二进制取反+1，
    * 如-10的二进制就是-1010=0101+1=0110，然后用1010&0110，答案就是0010
    *
    * */
    public static int lowbit(int k) {
        return k & (-k);
    }

    public static void add(int k, int num) {
        while (k < n) {
            tree[k] += num;
            k += lowbit(k);
        }
    }

    /*
    * 计算 1到K的和
    * */
    public static int sum(int k) {
        int sum = 0;
        while (k > 0) {
            sum += tree[k];
            k -= lowbit(k);
        }
        return sum;
    }

    public static void main(String[] args) {

        /*初始化tree数组*/
        for (int i = 1; i < n - 1; i++) {
            add(i, i);
        }

        System.out.println(sum(2) + "  " + addFor(2));
        System.out.println(sum(5) + "  " + addFor(5));
        System.out.println(sum(8) + "  " + addFor(8));


        //for (int i = 1; i < n; i++) {
        //    int k = i;
        //    System.out.println("--- "+ i +" ---");
        //    int temp=0;
        //    while (k > 0) {
        //        System.out.println(Integer.toBinaryString(k));
        //        temp += tree[k];
        //        k -= lowbit(k);
        //    }
        //    tree[i]=temp;
        //    System.out.println(temp);
        //}
        //for (int i = 0; i < tree.length; i++) {
        //    System.out.println(i+" -> "+ tree[i]);
        //}
    }

    /*最常见的累计 sum+=i*/
    static int addFor(int k) {
        int sum = 0;
        for (int i = 1; i <= k; i++) {
            sum += i;
        }
        return sum;
    }
}
